package com.algorithm.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

public class HorseChessBoard {
    private static int X;  //表示棋盘的列数
    private static int Y;  //表示棋盘的行数
    //记录棋盘中已被访问的位置
    private static boolean visited[][];
    //是否已经完成了
    private static boolean finished;

    public static void main(String[] args) {
        X = 8;
        Y = 8;
        int row = 1;
        int col = 1;
        int[][] chessBoard = new int[X][Y];
        //visited = new boolean[X][Y];
        visited = new boolean[X][Y];
        long start = System.currentTimeMillis();
        traversalChessBoard(chessBoard, row - 1, col - 1, 1);
        long end = System.currentTimeMillis();

        System.out.println("耗时:"+(end-start));

        for (int[] rows:chessBoard){
            for (int step: rows){
                System.out.format("%3d",step);
            }
            System.out.println();
        }
    }

    /**
     * 根据当前的点，计算可以走哪些点（最多8个，将这些点放入集合中
     *
     * @param curPoint
     * @return
     */
    public static ArrayList<Point> next(Point curPoint) {
        ArrayList<Point> ps = new ArrayList<>();
        //计算哪些点可以被访问
        Point p1 = new Point();
        //依次列出可以走的八个位置，并判断是否越界
        //用二维数组表示棋盘，左上角为(0,0)，所以y-1表示往上移动1位
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }
    /**
     * 获取当前这一步下一步的下一步所有可能的位置，进行非递减排序
     */
    public static void sort(ArrayList<Point> ps){
        ps.sort((o1, o2) -> next(o1).size()-next(o2).size());
    }

    /**
     * 马踏棋盘算法
     *
     * @param chessBoard 棋盘
     * @param row        起始点的行
     * @param col        起始点的列
     * @param step       步数
     */
    public static void traversalChessBoard(int[][] chessBoard, int row, int col, int step) {
        //1.将起始点设置为已访问的点，并标记步数
        chessBoard[row][col] = step;
        visited[row][col] = true;
        //2.获取当前位置可以走的集合,遍历集合中所有可能走的点，可以走就走，不能走回溯
        ArrayList<Point> next = next(new Point(col, row));
        //对next中所有的对象的下一位置次数进行非递减排序
        sort(next);
        while (!next.isEmpty()) {
            //3.取出下一个可以走的位置，判断该点是否已经被访问
            Point point = next.remove(0);
            if (!visited[point.y][point.x]) {
                traversalChessBoard(chessBoard, point.y, point.x, step + 1);
            }
        }
        //4.while循环结束以后，即表示已经没有可以走的点了
        // 此时如果还未完成任务，即进行回溯，即回到上一层循环中，取下一个位置
        if (step < X * Y && !finished) {
            chessBoard[row][col] = 0;
            visited[row][col] = false;
        } else {
            //用于结束回溯的过程
            finished = true;
        }
    }
}
